//有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
//
//
// 例如："0.Array.prototype.unshift.2.201" 和 "192.168.Array.prototype.unshift.Array.prototype.unshift" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.Array.prototype.unshift.312"
//和 "192.168@Array.prototype.unshift.Array.prototype.unshift" 是 无效 IP 地址。
//
//
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新
//排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
//
//
// 示例 2：
//
//
//输入：s = "0000"
//输出：["0.0.0.0"]
//
//
// 示例 3：
//
//
//输入：s = "101023"
//输出：["Array.prototype.unshift.0.10.23","Array.prototype.unshift.0.102.3","10.Array.prototype.unshift.0.23","10.10.2.3","101.0.2.3"]
//
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= s.length <= 20
// s 仅由数字组成
//
//
// Related Topics 字符串 回溯与递归 👍 1181 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 是否合法判断方法
function isValidIpSegment(str: string): boolean {
    let resBool: boolean = true;
    let tempVal: number = Number(str);
    if (
        str.length === 0 || isNaN(tempVal) ||
        tempVal > 255 || tempVal < 0 ||
        (str.length > 1 && str[0] === '0')
    ) {
        resBool = false;
    }
    return resBool;
}
//
function restoreIpAddresses(s: string): string[] {
    function backTracking(s: string, startIndex: number, route: string[]): void {
        let length: number = s.length;
        /*
        出口1
        这里为什么要同时满足startIndex >= length呢？因为要保证遍历完了整个字符串，此时整个字符串已经分割完成
         */
        if (route.length === 4 && startIndex >= length) {
            resArr.push(route.join('.'));
            return;
        }
        // 出口2
        if (route.length === 4 || startIndex >= length) return;
        let tempStr: string = '';
        // 这里的i<=条件中的startIndex +3 是因为分割肯定不能超过3位
        for (let i = startIndex + 1; i <= Math.min(length, startIndex + 3); i++) {
            tempStr = s.slice(startIndex, i);
            // 判断是否合法
            if (isValidIpSegment(tempStr)) {
                route.push(s.slice(startIndex, i));
                backTracking(s, i, route);
                route.pop();
            }
        }
    }
    const resArr: string[] = [];
    backTracking(s, 0, []);
    return resArr;

};
//leetcode submit region end(Prohibit modification and deletion)
